package oj0329.oj0329_03;

import javax.xml.soap.Node;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class ShareStack{
    private static final int stackSize = 10000;
    private int[] data;
    private int top1,top2;

    public ShareStack(){
        data = new int[stackSize];
        top1 = -1;
        top2 = stackSize;
    }


//    判断是否为空栈
    public boolean isEmpty(int i){
        if (i == 1) {
            return top1 == -1;
        } else {
            return top2 == stackSize;
        }
    }
//  判断是否栈满
    public boolean isFull(){
        return top2 == top1 + 1;
    }

//    入栈
    public void push(int i, int x){
        if (isFull()){
            return;
        }
        if (i == 1) {
            data[++top1] = x;
        }else {
            data[--top2] = x;
        }
    }

//    出栈
    public int pop(int i){
        if (i == 1) {
            if (isEmpty(i)){
                return -1;
            }
            return data[top1--];
        }else {
            if (isEmpty(i)){
                return -1;
            }
            return data[top2++];
        }
    }


}

public class Main {
    public static void main(String[] args) {
        ShareStack stack = new ShareStack();
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();  //数组元素个数
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }

//        入栈
        for (int el : a){
            if (el % 2 != 0){       //奇数
                stack.push(1,el);
            } else{
                stack.push(2,el);
            }
        }

        // 奇数栈
        StringBuilder sb1 = new StringBuilder();
        while (!stack.isEmpty(1)) {
            sb1.append(stack.pop(1)).append(" ");
        }
        sb1.append("\n");

        // 偶数栈
        StringBuilder sb2 = new StringBuilder();
        while (!stack.isEmpty(2)) {
            sb2.append(stack.pop(2)).append(" ");
        }
        sb2.append("\n");

        System.out.print(sb1);
        System.out.print(sb2);

        scanner.close();
    }
}
